【Leetcode】【python】Subsets Subsets II 子集 子集 II

Subsets

题目大意

给定一个由不同数字组成的集合，罗列出该集合的所有子集。

解题思路

见下方代码

代码

纯思路

参考：
https://shenjie1993.gitbooks.io/leetcode-python/078%20Subsets.html
举个例子，集合[1]有[[],[1]]两个子集，当向其中添加一个元素时，[1,2]有[[],[1],[2],[1,2]]四个子集，可以看出来，在新添加一个元素的时候，是在原来子集的基础上，添加原子集中所有元素加上新元素的总集合。为了每个子集中的元素都是不降序的，要先把所有元素都排序。

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = [[]]
        for num in sorted(nums):
            result += [item + [num] for item in result]
        return result

沿用排列题DFS

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        self.result = []
        nums.sort()
        for i in range(0, len(nums)+1):
            self.k = i
            self.combineHelper(0, [], nums)
        return self.result

    def combineHelper(self, length, temp, list_num):
        if length == self.k:
            self.result.append(temp[:])  # 需要用切片浅复制出一个新数组
            return
        for i, num in enumerate(list_num):
            temp.append(num)
            self.combineHelper(length+1, temp, list_num[i+1:])
            temp.pop()

Subsets II

题目大意

给定一个由不同数字组成的集合，罗列出该集合的所有子集。
有重复

解题思路

和上一题相同，问题在于如果有重复则会生成多余的子集。
参考：https://shenjie1993.gitbooks.io/leetcode-python/078%20Subsets.html
现在举个例子，集合[1]有[[],[1]]两个子集，当向其中添加一个元素时，[1,2]有[[],[1],[2],[1,2]]四个子集，可以看出来，在新添加一个元素的时候，是在原来子集的基础上，添加原子集中所有元素加上新元素的总集合。为了每个子集中的元素都是不降序的，要先把所有元素都排序。

代码

沿用排列题DFS

class Solution(object):
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = [[]]
        nums.sort()  # sort()直接修改原数组，sorted()返回排序后的数组，不修改原数组
        temp_size = 0
        for i in range(len(nums)):
            start = temp_size if i >= 1 and nums[i] == nums[i - 1] else 0
            temp_size = len(result)  # 每次取到result最后一位，也就是从start一直到最后一位
            for j in range(start, temp_size):
                result.append(result[j] + [nums[i]])
            print result
        return result

总结

纯思路做法显然效率更高，此题标签还有位运算做法，有空。